package study.datastructure.search;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-06-25 22:07
 */

import java.util.Arrays;

/**
 2024/6/25,
 */

//哨兵技巧
public class LinearSearchWithSentinel {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int key = 7;
        int result = linearSearchWithSentinel(arr, key);
        System.out.println("Element found at index: " + result);
    }

    private static int linearSearchWithSentinel(int[] arr, int key) {
        int [] extendedArr= Arrays.copyOf(arr,arr.length+1);
        extendedArr[extendedArr.length-1]=key;// 设置哨兵值为查找的值
        int i=0;
        while (extendedArr[i]!=key) {
            i++;
        }

        if(i<arr.length){
            return i;
        }else {
            return -1;
        }
    }
}
